package com.code.leetcode.center50.树的遍历;

import com.code.leetcode.utils.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/26 12:38
 */
public class The106 {
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int idx = 0;
        int len = inorder.length - 1;
        for (int num : inorder) {
            map.put(num, idx++);
        }
        return helper(inorder, postorder, 0, len, 0, len);
    }

    public TreeNode helper(int[] inorder, int[] postorder, int in_left, int in_right, int post_left, int post_right) {
        if (post_left > post_right) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[post_right]);
        int index = map.get(postorder[post_right]);
        int len = index - in_left;
        node.left = helper(inorder, postorder, in_left, index - 1, post_left, post_left + (index - 1 - in_left));
        node.right = helper(inorder, postorder, index + 1, in_right, post_right - in_right + index, post_right - 1);
        return node;
    }
}
